package mao.leetcode.others.leetcode105;

import java.util.HashMap;
import java.util.Map;

public class Solution {

    private static Map<Integer, Integer> map = new HashMap<>();  //节约每次查找的时间
    public static void main(String[] args) {
        int[] pre = {1,2,3};
        int[] in = {3,2,1};
        buildTree(pre,in);
    }

    public  static TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) return null;
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i],i);
        }
         return helper(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }

    public static TreeNode helper(int[] preorder, int startPre,int endPre,int[] inorder,int startIn,int endIn) {
        if (startPre > endPre) return null;
        if (startPre == endPre) return new TreeNode(preorder[startPre]);
        TreeNode root = new TreeNode(preorder[startPre]);
        int i = map.get(preorder[startPre]);
        int bais = i-startIn;
        root.left = helper(preorder,startPre+1,startPre+bais,inorder,startIn,i-1);  //对于前序遍历数组需要考虑数组的偏移
        root.right = helper(preorder,bais+startPre+1,endPre,inorder,i+1,endIn);
        return root;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}
